class Solution:
    def jump(self, nums):
        n = len(nums)
        if n == 1:
            return 0
        max_reach = 0
        end = 0
        jump = 0

        for i in range(n-1):
            max_reach = max(max_reach, i+nums[i])
            if i == end:
                jump += 1
                end = max_reach

                # 提前结束
                if end >= n-1:
                    break
        return jump
if __name__ == '__main__':
    nums = [2,3,1,1,4]
    print(Solution().jump(nums))

# max_pos：记录从当前跳跃区间内任意位置起跳能到达的最远位置

# end：记录当前跳跃能到达的边界（即这次跳跃能到达的最远位置）

# jumps：记录已经进行的跳跃次数